package zuochengyun;

/**
 * 使用位运算实现加减乘除
 */
public class BitOperateAddSubMulti {

	/**
	 * 加
	 */
	public int add(int a, int b) {
		int sum = 0;
		while(b != 0){
			//对于没有进位的二进制而言，异或的结果就是相加的结果
			sum = a ^ b;
			//a + b 所有的进位是(a & b) << 1
			//比如a ： 001010101  
			//    b:  000101111
			//(a & b) << 1: 00001010 
			//也就是只考虑进位的值
			b = (a & b) << 1;
		}
		return sum;
	}
	
	/**
	 * 减, a - b
	 */
	public int minus(int a, int b){
		return add(a, negNum(b));
	}
	
	private int negNum(int n){
		//得到一个数的相反数就是取反加1(补码)
		return add(~n, 1);
	}
	
	/**
	 * 乘
	 * a * b = a * 2^0 * b0 + a * 2^1 * b1 +.... + a * 2^31 * b31
	 * bi表示b的第i位
	 */
	public int multi(int a, int b){
		int res = 0;
		while(b != 0){
			if((b & 1) != 0){
				res = add(res, a);
				a <<= 1;
				b >>>= 1;
			}
		}
		return res;
	}
	
	/**
	 * 除，a / b
	 * 除采取的方法是逐步减去一个结果，然后获取到最后的结果
	 * 比如 a , b.  将b左移31位，30位...直到a 大于等于b，记录此时移动到第几位，商的该位设为1
	 */
	private int div(int a, int b){
		int x = isNeg(a) ? negNum(a) : a;
		int y = isNeg(b) ? negNum(b) : b;
		int res = 0;
		for (int i = 31; i >= 0; i--) {
			if((y << i)  <= x){
				res |= (1 << i);
				//更新x的值
				x = minus(x, y << i);
			}
		}
		//如果两者的符号相同就直接返回res，如果符号不相同则返回相反数
		return (isNeg(a) ^ isNeg(b)) ? negNum(res) : res;
	}
	
	/**
	 * 上面的div解法有问题，因为负数比正数的范围大1，可能导致获取到正数的时候产生溢出
	 * @return
	 */
	public int divide(int a, int b){
		if(b == 0){
			throw new RuntimeException("divisor is 0");
		}
		if(a == Integer.MIN_VALUE && b == Integer.MIN_VALUE){
			return 1;
		}else if(b == Integer.MIN_VALUE){
			return 0;
		}else if(a == Integer.MIN_VALUE){
			//如果a为最小值，b不为最小值
			//先计算(a + 1) / b的值然后再去修正 
			int res = div(add(a, 1), b);
			//下面就是该式子的运算  (a - res * b) / b + res
			return add(res, div( (minus(a, multi(res, b))) , b));
		}else{
			return div(a, b);
		}
	}
	
	public boolean isNeg(int n){
		return n < 0;
	}
}
